i=1∑nj=1∑mij(i,j)μ2((i,j))
k=1∑min(n,m)i=1∑nj=1∑m[(i,j)=k]ijkμ2(k)
k=1∑min(n,m)k3μ2(k)i=1∑⌊kn⌋j=1∑⌊km⌋[(i,j)=1]ij
k=1∑min(n,m)k3μ2(k)d=1∑min(⌊kn⌋,⌊km⌋)μ(d)d2i=1∑⌊kdn⌋j=1∑⌊kdm⌋ij
k=1∑min(n,m)dk=1∑min(n,m)k3μ2(k)μ(d)d2i=1∑⌊kdn⌋j=1∑⌊kdm⌋ij
令 s(n)=2n(n+1)
T=1∑min(n,m)T2s(⌊Tn⌋)s(⌊Tm⌋)k∣T∑kμ2(k)μ(kT)
令 f(n)=∑d∣ndμ2(d)μ(dn)
T=1∑min(n,m)T2f(T)s(⌊Tn⌋)s(⌊Tm⌋)
首先由狄利克雷卷积的性质,f(n) 是一个积性函数,考虑线性筛。
首先如果 n 的质因子数量出现 3 次以上,那么 d 和 dn 一定有一个有平方因子,μ 为 0。
那么每个质因子只能出现 1 次或 2 次。
f(p)=1μ2(1)μ(p)+pμ2(p)μ(1)=p−1
f(p2)=1μ2(1)μ(p2)+pμ2(p)μ(p)+p2μ2(p2)μ(1)=−p
f(1)=1 ,线筛后乘上 i2 做前缀和就可以整除分块。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e6 , Mod = 1e9 + 7;
int prn , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) { prime[ ++ prn ] = i , f[ i ] = i - 1; }
for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
if( ( i / prime[ j ] ) % prime[ j ] ) f[ i * prime[ j ] ] = 1ll * f[ i / prime[ j ] ] * ( Mod - prime[ j ] ) % Mod;
break;
}
f[ i * prime[ j ] ] = 1ll * f[ i ] * f[ prime[ j ] ] % Mod;
}
}
for( int i = 1 ; i <= MAXN ; i ++ ) f[ i ] = ( f[ i - 1 ] + 1ll * f[ i ] * i % Mod * i % Mod ) % Mod;
}
int Sum1( int n ) {
return 1ll * n * ( n + 1 ) / 2 % Mod;
}
int Solve( int n , int m ) {
int k = min( n , m ) , Ans = 0;
for( int l = 1 , r ; l <= k ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * Sum1( n / l ) % Mod * Sum1( m / l ) % Mod ) % Mod;
}
return Ans;
}
int t , n , m;
int main( ) {
sieve( );
scanf("%d",&t);
for( int i = 1 ; i <= t ; i ++ ) {
scanf("%d %d",&n,&m);
printf("%d\n", Solve( n , m ) );
}
return 0;
}